package answer

import (
	"sort"
)

func topKFrequent(words []string, k int) []string {
	tempMap := make(map[string]int)
	for _, word := range words {
		tempMap[word]++
	}

	pairList := sortMapByValue(tempMap)
	result := make([]string, 0)
	for _, pair := range pairList {
		result = append(result, pair.Key)
	}
	return result[:k]

}

type PairList []Pair

type Pair struct {
	Key   string
	Value int
}

func (p PairList) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p PairList) Len() int      { return len(p) }
func (p PairList) Less(i, j int) bool {
	if p[i].Value == p[j].Value {
		return p[i].Key > p[j].Key
	}
	return p[i].Value < p[j].Value
}

func sortMapByValue(m map[string]int) PairList {
	p := make(PairList, len(m))
	i := 0
	for k, v := range m {
		p[i] = Pair{k, v}
		i++
	}
	sort.Sort(sort.Reverse(p)) // sort.Reverse是提供倒序排序
	return p
}
